//! import "common\Base.j"

library Tree requires Base

///////////////////////////////////////////////////////////////////////////////////////////////////////////////
// //! runtextmacro Tree("type", "Name", "compare function", "destroy function")
// //! runtextmacro TreeSimple("type", "Name")
// //! runtextmacro TreeChild("type", "Name", "compare function", "destroy function")
// //! runtextmacro TreeChildSimple("type", "Name")
//     Find Insert Get GetFirst GetNext Delete Clear GetSize
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

//! textmacro Tree takes type, name, compare, destroy
private struct $name$
	private static $type$ array Keys
	private static integer array Value
	private static integer array LChild
	private static integer array RChild
	private static integer array Parent
	private static integer Root = 0
	private static integer Top = 1
	private static integer Size = 0

	private static integer array Index
	private static integer array Backward
	private static integer IndexTop = 1

	private static method New takes $type$ key returns integer
		local integer i = Top
		if i > GetArrayMaxSize() then
			call Error()
			return 0
		endif
		if Value[Top] == 0 then
			set Top = Top + 1
		else
			set Top = Value[Top]
		endif
		set Keys[i] = key
		set Value[i] = 1
		set LChild[i] = 0
		set RChild[i] = 0
		set Index[i] = IndexTop
		if Backward[IndexTop] == 0 then
			set IndexTop = IndexTop + 1
		else
			set IndexTop = Backward[IndexTop]
		endif
		set Backward[Index[i]] = i
		return i
	endmethod

	private static method Free takes integer i returns nothing
		call $destroy$(Keys[i])
		set Backward[Index[i]] = IndexTop
		set IndexTop = Index[i]
		set Value[i] = Top
		set Top = i
	endmethod

	private static method AjustValue takes integer i returns nothing
		local integer l
		local integer r
		if LChild[i] == 0 then
			set l = 0
		else
			set l = Value[LChild[i]]
		endif
		if RChild[i] == 0 then
			set r = 0
		else
			set r = Value[RChild[i]]
		endif
		if l > r then
			set Value[i] = l + 1
		else
			set Value[i] = r + 1
		endif
	endmethod

	private static method Left takes integer i returns nothing
		local integer c = RChild[i]
		set RChild[i] = LChild[c]
		set LChild[c] = i
		if RChild[i] != 0 then
			set Parent[RChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root = c
		else
			if RChild[Parent[c]] == i then
				set RChild[Parent[c]] = c
			else
				set LChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Right takes integer i returns nothing
		local integer c = LChild[i]
		set LChild[i] = RChild[c]
		set RChild[c] = i
		if LChild[i] != 0 then
			set Parent[LChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root = c
		else
			if LChild[Parent[c]] == i then
				set LChild[Parent[c]] = c
			else
				set RChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Swap takes integer i, integer j returns nothing
		local $type$ k = Keys[i]
		local integer n = Index[i]
		set Keys[i] = Keys[j]
		set Index[i] = Index[j]
		set Keys[j] = k
		set Index[j] = n
		set Backward[Index[i]] = i
		set Backward[Index[j]] = j
	endmethod

	private static method AjustWork takes integer n, integer m, integer i returns nothing
		local integer c
		local integer l
		local integer r
		set Value[n] = m + 1
		if i > 1 then
			set c = RChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l < 0 then
				call Right(c)
				call Left(n)
			else
				call Left(n)
			endif
		elseif i < -1 then
			set c = LChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l > 0 then
				call Left(c)
				call Right(n)
			else
				call Right(n)
			endif
		endif
	endmethod

	private static method Ajust takes integer i returns nothing
		local integer n = i
		local integer l
		local integer r
		loop
			exitwhen n == 0
			if LChild[n] == 0 then
				set l = 0
			else
				set l = Value[LChild[n]]
			endif
			if RChild[n] == 0 then
				set r = 0
			else
				set r = Value[RChild[n]]
			endif
			set l = r - l
			if l < 0 then
				set r = r - l
			endif
			if Value[n] == r + 1 and l < 2 and l > -2 then
				exitwhen true
			endif
			call AjustWork(n, r, l)
			set n = Parent[n]
		endloop
	endmethod

	static method Find takes $type$ key returns integer
		local integer i = Root
		local integer j
		loop
			exitwhen i == 0
			set j = $compare$(key, Keys[i])
			if j > 0 then
				set i = RChild[i]
			elseif j < 0 then
				set i = LChild[i]
			else
				exitwhen true
			endif
		endloop
		call $destroy$(key)
		return Index[i]
	endmethod

	static method Insert takes $type$ key returns integer
		local integer i
		local integer j
		local integer k
		if Root == 0 then
			set i = New(key)
			set Parent[i] = 0
			set Root = i
		else
			set i = Root
			loop
				set j = $compare$(key, Keys[i])
				if j > 0 then
					set k = RChild[i]
				elseif j < 0 then
					set k = LChild[i]
				else
					exitwhen true
				endif
				exitwhen k == 0
				set i = k
			endloop
			if j == 0 then
				call $destroy$(key)
			else
				set k = i
				set i = New(key)
				set Parent[i] = k
				if j > 0 then
					set RChild[k] = i
				else
					set LChild[k] = i
				endif
				call Ajust(k)
				set Size = Size + 1
			endif
		endif
		return Index[i]
	endmethod

	static method Get takes integer index returns $type$
		return Keys[Backward[index]]
	endmethod

	private static method FindMaxLeft takes integer i returns integer
		if i == 0 then
			return 0
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		return i
	endmethod

	static method GetFirst takes nothing returns integer
		return Index[FindMaxLeft(Root)]
	endmethod

	static method GetNext takes integer i returns integer
		set i = Backward[i]
		if RChild[i] == 0 then
			loop
				exitwhen Parent[i] == 0 or LChild[Parent[i]] == i
				set i = Parent[i]
			endloop
			return Index[Parent[i]]
		endif
		return Index[FindMaxLeft(RChild[i])]
	endmethod

	static method Delete takes integer index returns integer
		local integer i = Backward[index]
		local integer n = RChild[i]
		local integer j
		if n == 0 then
			set n = Parent[i]
			if n == 0 then
				set Root = LChild[i]
				if Root != 0 then
					set Parent[Root] = 0
				endif
			else
				set j = n
				if LChild[n] == i then
					set LChild[n] = LChild[i]
				else
					set RChild[n] = LChild[i]
					loop
						exitwhen Parent[j] == 0 or LChild[Parent[j]] == j
						set j = Parent[j]
					endloop
					set j = Parent[j]
				endif
				set Parent[LChild[i]] = n
				call Ajust(n)
				set n = j
			endif
		else
			set n = FindMaxLeft(n)
			set j = n
			loop
				call Swap(i, j)
				set i = i
				set j = RChild[i]
				exitwhen j == 0
				set j = FindMaxLeft(j)
			endloop
			if LChild[Parent[i]] == i then
				set LChild[Parent[i]] = 0
			else
				set RChild[Parent[i]] = 0
			endif
			call Ajust(Parent[i])
		endif
		call Free(i)
		set Size = Size - 1
		return Index[n]
	endmethod

	static method Clear takes nothing returns nothing
		local integer i = Root
		local integer j
		if i == 0 then
			return
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		loop
			exitwhen RChild[i] == 0
			set i = RChild[i]
		endloop
		loop
			set j = Parent[i]
			call Free(i)
			exitwhen j == 0
			if LChild[j] == i then
				if RChild[j] == 0 then
					set i = j
				else
					set i = RChild[j]
					loop
						exitwhen LChild[i] == 0
						set i = LChild[i]
					endloop
					loop
						exitwhen RChild[i] == 0
						set i = RChild[i]
					endloop
				endif
			else
				set i = j
			endif
		endloop
		set Root = 0
		set Size = 0
	endmethod

	static method GetSize takes nothing returns integer
		return Size
	endmethod
endstruct
//! endtextmacro

//! textmacro TreeSimple takes type, name
private struct $name$
	private static $type$ array Keys
	private static integer array Value
	private static integer array LChild
	private static integer array RChild
	private static integer array Parent
	private static integer Root = 0
	private static integer Top = 1
	private static integer Size = 0

	private static integer array Index
	private static integer array Backward
	private static integer IndexTop = 1

	private static method New takes $type$ key returns integer
		local integer i = Top
		if i > GetArrayMaxSize() then
			call Error()
			return 0
		endif
		if Value[Top] == 0 then
			set Top = Top + 1
		else
			set Top = Value[Top]
		endif
		set Keys[i] = key
		set Value[i] = 1
		set LChild[i] = 0
		set RChild[i] = 0
		set Index[i] = IndexTop
		if Backward[IndexTop] == 0 then
			set IndexTop = IndexTop + 1
		else
			set IndexTop = Backward[IndexTop]
		endif
		set Backward[Index[i]] = i
		return i
	endmethod

	private static method Free takes integer i returns nothing
		set Backward[Index[i]] = IndexTop
		set IndexTop = Index[i]
		set Value[i] = Top
		set Top = i
	endmethod

	private static method AjustValue takes integer i returns nothing
		local integer l
		local integer r
		if LChild[i] == 0 then
			set l = 0
		else
			set l = Value[LChild[i]]
		endif
		if RChild[i] == 0 then
			set r = 0
		else
			set r = Value[RChild[i]]
		endif
		if l > r then
			set Value[i] = l + 1
		else
			set Value[i] = r + 1
		endif
	endmethod

	private static method Left takes integer i returns nothing
		local integer c = RChild[i]
		set RChild[i] = LChild[c]
		set LChild[c] = i
		if RChild[i] != 0 then
			set Parent[RChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root = c
		else
			if RChild[Parent[c]] == i then
				set RChild[Parent[c]] = c
			else
				set LChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Right takes integer i returns nothing
		local integer c = LChild[i]
		set LChild[i] = RChild[c]
		set RChild[c] = i
		if LChild[i] != 0 then
			set Parent[LChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root = c
		else
			if LChild[Parent[c]] == i then
				set LChild[Parent[c]] = c
			else
				set RChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Swap takes integer i, integer j returns nothing
		local $type$ k = Keys[i]
		local integer n = Index[i]
		set Keys[i] = Keys[j]
		set Index[i] = Index[j]
		set Keys[j] = k
		set Index[j] = n
		set Backward[Index[i]] = i
		set Backward[Index[j]] = j
	endmethod

	private static method AjustWork takes integer n, integer m, integer i returns nothing
		local integer c
		local integer l
		local integer r
		set Value[n] = m + 1
		if i > 1 then
			set c = RChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l < 0 then
				call Right(c)
				call Left(n)
			else
				call Left(n)
			endif
		elseif i < -1 then
			set c = LChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l > 0 then
				call Left(c)
				call Right(n)
			else
				call Right(n)
			endif
		endif
	endmethod

	private static method Ajust takes integer i returns nothing
		local integer n = i
		local integer l
		local integer r
		loop
			exitwhen n == 0
			if LChild[n] == 0 then
				set l = 0
			else
				set l = Value[LChild[n]]
			endif
			if RChild[n] == 0 then
				set r = 0
			else
				set r = Value[RChild[n]]
			endif
			set l = r - l
			if l < 0 then
				set r = r - l
			endif
			if Value[n] == r + 1 and l < 2 and l > -2 then
				exitwhen true
			endif
			call AjustWork(n, r, l)
			set n = Parent[n]
		endloop
	endmethod

	static method Find takes $type$ key returns integer
		local integer i = Root
		loop
			exitwhen i == 0
			if key > Keys[i] then
				set i = RChild[i]
			elseif key < Keys[i] then
				set i = LChild[i]
			else
				exitwhen true
			endif
		endloop
		return Index[i]
	endmethod

	static method Insert takes $type$ key returns integer
		local integer i
		local integer k
		if Root == 0 then
			set i = New(key)
			set Parent[i] = 0
			set Root = i
		else
			set i = Root
			loop
				if key > Keys[i] then
					set k = RChild[i]
				elseif key < Keys[i] then
					set k = LChild[i]
				else
					exitwhen true
				endif
				exitwhen k == 0
				set i = k
			endloop
			if key != Keys[i] then
				set k = i
				set i = New(key)
				set Parent[i] = k
				if key > Keys[k] then
					set RChild[k] = i
				else
					set LChild[k] = i
				endif
				call Ajust(k)
				set Size = Size + 1
			endif
		endif
		return Index[i]
	endmethod

	static method Get takes integer index returns $type$
		return Keys[Backward[index]]
	endmethod

	private static method FindMaxLeft takes integer i returns integer
		if i == 0 then
			return 0
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		return i
	endmethod

	static method GetFirst takes nothing returns integer
		return Index[FindMaxLeft(Root)]
	endmethod

	static method GetNext takes integer i returns integer
		set i = Backward[i]
		if RChild[i] == 0 then
			loop
				exitwhen Parent[i] == 0 or LChild[Parent[i]] == i
				set i = Parent[i]
			endloop
			return Index[Parent[i]]
		endif
		return Index[FindMaxLeft(RChild[i])]
	endmethod

	static method Delete takes integer index returns integer
		local integer i = Backward[index]
		local integer n = RChild[i]
		local integer j
		if n == 0 then
			set n = Parent[i]
			if n == 0 then
				set Root = LChild[i]
				if Root != 0 then
					set Parent[Root] = 0
				endif
			else
				set j = n
				if LChild[n] == i then
					set LChild[n] = LChild[i]
				else
					set RChild[n] = LChild[i]
					loop
						exitwhen Parent[j] == 0 or LChild[Parent[j]] == j
						set j = Parent[j]
					endloop
					set j = Parent[j]
				endif
				set Parent[LChild[i]] = n
				call Ajust(n)
				set n = j
			endif
		else
			set n = FindMaxLeft(n)
			set j = n
			loop
				call Swap(i, j)
				set i = i
				set j = RChild[i]
				exitwhen j == 0
				set j = FindMaxLeft(j)
			endloop
			if LChild[Parent[i]] == i then
				set LChild[Parent[i]] = 0
			else
				set RChild[Parent[i]] = 0
			endif
			call Ajust(Parent[i])
		endif
		call Free(i)
		set Size = Size - 1
		return Index[n]
	endmethod

	static method Clear takes nothing returns nothing
		local integer i = Root
		local integer j
		if i == 0 then
			return
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		loop
			exitwhen RChild[i] == 0
			set i = RChild[i]
		endloop
		loop
			set j = Parent[i]
			call Free(i)
			exitwhen j == 0
			if LChild[j] == i then
				if RChild[j] == 0 then
					set i = j
				else
					set i = RChild[j]
					loop
						exitwhen LChild[i] == 0
						set i = LChild[i]
					endloop
					loop
						exitwhen RChild[i] == 0
						set i = RChild[i]
					endloop
				endif
			else
				set i = j
			endif
		endloop
		set Root = 0
		set Size = 0
	endmethod

	static method GetSize takes nothing returns integer
		return Size
	endmethod
endstruct
//! endtextmacro

//! textmacro TreeChild takes type, name, compare, destroy
private struct $name$
	private static $type$ array Keys
	private static integer array Value
	private static integer array LChild
	private static integer array RChild
	private static integer array Parent
	private static integer array Root
	private static integer Top = 1
	private static integer Size = 0

	private static integer array Index
	private static integer array Backward
	private static integer IndexTop = 1

	private static method New takes $type$ key returns integer
		local integer i = Top
		if i > GetArrayMaxSize() then
			call Error()
			return 0
		endif
		if Value[Top] == 0 then
			set Top = Top + 1
		else
			set Top = Value[Top]
		endif
		set Keys[i] = key
		set Value[i] = 1
		set LChild[i] = 0
		set RChild[i] = 0
		set Index[i] = IndexTop
		if Backward[IndexTop] == 0 then
			set IndexTop = IndexTop + 1
		else
			set IndexTop = Backward[IndexTop]
		endif
		set Backward[Index[i]] = i
		return i
	endmethod

	private static method Free takes integer i returns nothing
		call $destroy$(Keys[i])
		set Backward[Index[i]] = IndexTop
		set IndexTop = Index[i]
		set Value[i] = Top
		set Top = i
	endmethod

	private static method AjustValue takes integer i returns nothing
		local integer l
		local integer r
		if LChild[i] == 0 then
			set l = 0
		else
			set l = Value[LChild[i]]
		endif
		if RChild[i] == 0 then
			set r = 0
		else
			set r = Value[RChild[i]]
		endif
		if l > r then
			set Value[i] = l + 1
		else
			set Value[i] = r + 1
		endif
	endmethod

	private static method Left takes integer root, integer i returns nothing
		local integer c = RChild[i]
		set RChild[i] = LChild[c]
		set LChild[c] = i
		if RChild[i] != 0 then
			set Parent[RChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root[root] = c
		else
			if RChild[Parent[c]] == i then
				set RChild[Parent[c]] = c
			else
				set LChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Right takes integer root, integer i returns nothing
		local integer c = LChild[i]
		set LChild[i] = RChild[c]
		set RChild[c] = i
		if LChild[i] != 0 then
			set Parent[LChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root[root] = c
		else
			if LChild[Parent[c]] == i then
				set LChild[Parent[c]] = c
			else
				set RChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Swap takes integer root, integer i, integer j returns nothing
		local $type$ k = Keys[i]
		local integer n = Index[i]
		set Keys[i] = Keys[j]
		set Index[i] = Index[j]
		set Keys[j] = k
		set Index[j] = n
		set Backward[Index[i]] = i
		set Backward[Index[j]] = j
	endmethod

	private static method AjustWork takes integer root, integer n, integer m, integer i returns nothing
		local integer c
		local integer l
		local integer r
		set Value[n] = m + 1
		if i > 1 then
			set c = RChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l < 0 then
				call Right(root, c)
				call Left(root, n)
			else
				call Left(root, n)
			endif
		elseif i < -1 then
			set c = LChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l > 0 then
				call Left(root, c)
				call Right(root, n)
			else
				call Right(root, n)
			endif
		endif
	endmethod

	private static method Ajust takes integer root, integer i returns nothing
		local integer n = i
		local integer l
		local integer r
		loop
			exitwhen n == 0
			if LChild[n] == 0 then
				set l = 0
			else
				set l = Value[LChild[n]]
			endif
			if RChild[n] == 0 then
				set r = 0
			else
				set r = Value[RChild[n]]
			endif
			set l = r - l
			if l < 0 then
				set r = r - l
			endif
			if Value[n] == r + 1 and l < 2 and l > -2 then
				exitwhen true
			endif
			call AjustWork(root, n, r, l)
			set n = Parent[n]
		endloop
	endmethod

	static method Find takes integer root, $type$ key returns integer
		local integer i = Root[root]
		local integer j
		loop
			exitwhen i == 0
			set j = $compare$(key, Keys[i])
			if j > 0 then
				set i = RChild[i]
			elseif j < 0 then
				set i = LChild[i]
			else
				exitwhen true
			endif
		endloop
		call $destroy$(key)
		return Index[i]
	endmethod

	static method Insert takes integer root, $type$ key returns integer
		local integer i
		local integer j
		local integer k
		if Root[root] == 0 then
			set i = New(key)
			set Parent[i] = 0
			set Root[root] = i
		else
			set i = Root[root]
			loop
				set j = $compare$(key, Keys[i])
				if j > 0 then
					set k = RChild[i]
				elseif j < 0 then
					set k = LChild[i]
				else
					exitwhen true
				endif
				exitwhen k == 0
				set i = k
			endloop
			if j == 0 then
				call $destroy$(key)
			else
				set k = i
				set i = New(key)
				set Parent[i] = k
				if j > 0 then
					set RChild[k] = i
				else
					set LChild[k] = i
				endif
				call Ajust(root, k)
				set Size = Size + 1
			endif
		endif
		return Index[i]
	endmethod

	static method Get takes integer index returns $type$
		return Keys[Backward[index]]
	endmethod

	private static method FindMaxLeft takes integer i returns integer
		if i == 0 then
			return 0
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		return i
	endmethod

	static method GetFirst takes integer root returns integer
		return Index[FindMaxLeft(Root[root])]
	endmethod

	static method GetNext takes integer i returns integer
		set i = Backward[i]
		if RChild[i] == 0 then
			loop
				exitwhen Parent[i] == 0 or LChild[Parent[i]] == i
				set i = Parent[i]
			endloop
			return Index[Parent[i]]
		endif
		return Index[FindMaxLeft(RChild[i])]
	endmethod

	static method Delete takes integer root, integer index returns integer
		local integer i = Backward[index]
		local integer n = RChild[i]
		local integer j
		if n == 0 then
			set n = Parent[i]
			if n == 0 then
				set Root[root] = LChild[i]
				set Parent[LChild[i]] = 0
			else
				set j = n
				if LChild[n] == i then
					set LChild[n] = LChild[i]
				else
					set RChild[n] = LChild[i]
					loop
						exitwhen Parent[j] == 0 or LChild[Parent[j]] == j
						set j = Parent[j]
					endloop
					set j = Parent[j]
				endif
				set Parent[LChild[i]] = n
				call Ajust(root, n)
				set n = j
			endif
		else
			set n = FindMaxLeft(n)
			set j = n
			loop
				call Swap(root, i, j)
				set j = RChild[i]
				exitwhen j == 0
				set j = FindMaxLeft(j)
			endloop
			if LChild[Parent[i]] == i then
				set LChild[Parent[i]] = 0
			else
				set RChild[Parent[i]] = 0
			endif
			call Ajust(root, Parent[i])
		endif
		call Free(i)
		set Size = Size - 1
		return Index[n]
	endmethod

	static method Clear takes integer root returns nothing
		local integer i = Root[root]
		local integer j
		if i == 0 then
			return
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		loop
			exitwhen RChild[i] == 0
			set i = RChild[i]
		endloop
		loop
			set j = Parent[i]
			call Free(i)
			exitwhen j == 0
			if LChild[j] == i then
				if RChild[j] == 0 then
					set i = j
				else
					set i = RChild[j]
					loop
						exitwhen LChild[i] == 0
						set i = LChild[i]
					endloop
					loop
						exitwhen RChild[i] == 0
						set i = RChild[i]
					endloop
				endif
			else
				set i = j
			endif
		endloop
		set Root[root] = 0
		set Size = 0
	endmethod

	static method GetSize takes nothing returns integer
		return Size
	endmethod
endstruct
//! endtextmacro

//! textmacro TreeChildSimple takes type, name
private struct $name$
	private static $type$ array Keys
	private static integer array Value
	private static integer array LChild
	private static integer array RChild
	private static integer array Parent
	private static integer array Root
	private static integer Top = 1
	private static integer Size = 0

	private static integer array Index
	private static integer array Backward
	private static integer IndexTop = 1

	private static method New takes $type$ key returns integer
		local integer i = Top
		if i > GetArrayMaxSize() then
			call Error()
			return 0
		endif
		if Value[Top] == 0 then
			set Top = Top + 1
		else
			set Top = Value[Top]
		endif
		set Keys[i] = key
		set Value[i] = 1
		set LChild[i] = 0
		set RChild[i] = 0
		set Index[i] = IndexTop
		if Backward[IndexTop] == 0 then
			set IndexTop = IndexTop + 1
		else
			set IndexTop = Backward[IndexTop]
		endif
		set Backward[Index[i]] = i
		return i
	endmethod

	private static method Free takes integer i returns nothing
		set Backward[Index[i]] = IndexTop
		set IndexTop = Index[i]
		set Value[i] = Top
		set Top = i
	endmethod

	private static method AjustValue takes integer i returns nothing
		local integer l
		local integer r
		if LChild[i] == 0 then
			set l = 0
		else
			set l = Value[LChild[i]]
		endif
		if RChild[i] == 0 then
			set r = 0
		else
			set r = Value[RChild[i]]
		endif
		if l > r then
			set Value[i] = l + 1
		else
			set Value[i] = r + 1
		endif
	endmethod

	private static method Left takes integer root, integer i returns nothing
		local integer c = RChild[i]
		set RChild[i] = LChild[c]
		set LChild[c] = i
		if RChild[i] != 0 then
			set Parent[RChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root[root] = c
		else
			if RChild[Parent[c]] == i then
				set RChild[Parent[c]] = c
			else
				set LChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Right takes integer root, integer i returns nothing
		local integer c = LChild[i]
		set LChild[i] = RChild[c]
		set RChild[c] = i
		if LChild[i] != 0 then
			set Parent[LChild[i]] = i
		endif
		set Parent[c] = Parent[i]
		set Parent[i] = c
		if Parent[c] == 0 then
			set Root[root] = c
		else
			if LChild[Parent[c]] == i then
				set LChild[Parent[c]] = c
			else
				set RChild[Parent[c]] = c
			endif
		endif
		call AjustValue(i)
		call AjustValue(c)
	endmethod

	private static method Swap takes integer root, integer i, integer j returns nothing
		local $type$ k = Keys[i]
		local integer n = Index[i]
		set Keys[i] = Keys[j]
		set Index[i] = Index[j]
		set Keys[j] = k
		set Index[j] = n
		set Backward[Index[i]] = i
		set Backward[Index[j]] = j
	endmethod

	private static method AjustWork takes integer root, integer n, integer m, integer i returns nothing
		local integer c
		local integer l
		local integer r
		set Value[n] = m + 1
		if i > 1 then
			set c = RChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l < 0 then
				call Right(root, c)
				call Left(root, n)
			else
				call Left(root, n)
			endif
		elseif i < -1 then
			set c = LChild[n]
			if LChild[c] == 0 then
				set l = 0
			else
				set l = Value[LChild[c]]
			endif
			if RChild[c] == 0 then
				set r = 0
			else
				set r = Value[RChild[c]]
			endif
			if r - l > 0 then
				call Left(root, c)
				call Right(root, n)
			else
				call Right(root, n)
			endif
		endif
	endmethod

	private static method Ajust takes integer root, integer i returns nothing
		local integer n = i
		local integer l
		local integer r
		loop
			exitwhen n == 0
			if LChild[n] == 0 then
				set l = 0
			else
				set l = Value[LChild[n]]
			endif
			if RChild[n] == 0 then
				set r = 0
			else
				set r = Value[RChild[n]]
			endif
			set l = r - l
			if l < 0 then
				set r = r - l
			endif
			if Value[n] == r + 1 and l < 2 and l > -2 then
				exitwhen true
			endif
			call AjustWork(root, n, r, l)
			set n = Parent[n]
		endloop
	endmethod

	static method Find takes integer root, $type$ key returns integer
		local integer i = Root[root]
		loop
			exitwhen i == 0
			if key > Keys[i] then
				set i = RChild[i]
			elseif key < Keys[i] then
				set i = LChild[i]
			else
				exitwhen true
			endif
		endloop
		return Index[i]
	endmethod

	static method Insert takes integer root, $type$ key returns integer
		local integer i
		local integer k
		if Root[root] == 0 then
			set i = New(key)
			set Parent[i] = 0
			set Root[root] = i
		else
			set i = Root[root]
			loop
				if key > Keys[i] then
					set k = RChild[i]
				elseif key < Keys[i] then
					set k = LChild[i]
				else
					exitwhen true
				endif
				exitwhen k == 0
				set i = k
			endloop
			if key != Keys[i] then
				set k = i
				set i = New(key)
				set Parent[i] = k
				if key > Keys[k] then
					set RChild[k] = i
				else
					set LChild[k] = i
				endif
				call Ajust(root, k)
				set Size = Size + 1
			endif
		endif
		return Index[i]
	endmethod

	static method Get takes integer index returns $type$
		return Keys[Backward[index]]
	endmethod

	private static method FindMaxLeft takes integer i returns integer
		if i == 0 then
			return 0
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		return i
	endmethod

	static method GetFirst takes integer root returns integer
		return Index[FindMaxLeft(Root[root])]
	endmethod

	static method GetNext takes integer i returns integer
		set i = Backward[i]
		if RChild[i] == 0 then
			loop
				exitwhen Parent[i] == 0 or LChild[Parent[i]] == i
				set i = Parent[i]
			endloop
			return Index[Parent[i]]
		endif
		return Index[FindMaxLeft(RChild[i])]
	endmethod

	static method Delete takes integer root, integer index returns integer
		local integer i = Backward[index]
		local integer n = RChild[i]
		local integer j
		if n == 0 then
			set n = Parent[i]
			if n == 0 then
				set Root[root] = LChild[i]
				set Parent[LChild[i]] = 0
			else
				set j = n
				if LChild[n] == i then
					set LChild[n] = LChild[i]
				else
					set RChild[n] = LChild[i]
					loop
						exitwhen Parent[j] == 0 or LChild[Parent[j]] == j
						set j = Parent[j]
					endloop
					set j = Parent[j]
				endif
				set Parent[LChild[i]] = n
				call Ajust(root, n)
				set n = j
			endif
		else
			set n = FindMaxLeft(n)
			set j = n
			loop
				call Swap(root, i, j)
				set j = RChild[i]
				exitwhen j == 0
				set j = FindMaxLeft(j)
			endloop
			if LChild[Parent[i]] == i then
				set LChild[Parent[i]] = 0
			else
				set RChild[Parent[i]] = 0
			endif
			call Ajust(root, Parent[i])
		endif
		call Free(i)
		set Size = Size - 1
		return Index[n]
	endmethod

	static method Clear takes integer root returns nothing
		local integer i = Root[root]
		local integer j
		if i == 0 then
			return
		endif
		loop
			exitwhen LChild[i] == 0
			set i = LChild[i]
		endloop
		loop
			exitwhen RChild[i] == 0
			set i = RChild[i]
		endloop
		loop
			set j = Parent[i]
			call Free(i)
			exitwhen j == 0
			if LChild[j] == i then
				if RChild[j] == 0 then
					set i = j
				else
					set i = RChild[j]
					loop
						exitwhen LChild[i] == 0
						set i = LChild[i]
					endloop
					loop
						exitwhen RChild[i] == 0
						set i = RChild[i]
					endloop
				endif
			else
				set i = j
			endif
		endloop
		set Root[root] = 0
		set Size = 0
	endmethod

	static method GetSize takes nothing returns integer
		return Size
	endmethod
endstruct
//! endtextmacro

endlibrary